package algorithm.niuke;

public class 区间子数组个数 {
    /*
     * 给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
     * 
     * 求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。
     * 
     * 例如 : 输入: A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1],
     * [3].
     * 
     * : 输入: A = [2, 2, 1, 4, 3] L = 2 R = 3 输出: 6 解释: 满足条件的子数组:
     * [2],[2,2],[2],[2,2,1],[2,1], [3].
     */
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        /*
         * 思路：1、所有大于R的数，都可以将数组A划分为2段 2、对于第i个元素，对于 A[i]<j<=R, dp[i][j]=
         * dp[i-1][j] + 1; 对于j<A[i], dp[i][A[i]] += dp[i-1][j];
         * 
         */
        int len = A.length;
        int[][] dp = new int[len][R + 5];
        dp[0][A[0]] = 1;
        for (int i = 1; i < len; i++) {
            if (A[i] > R) {
                continue;
            }
            for (int j = A[i]; j <= R; j++) {
                if (dp[i - 1][j] > 0) {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            for (int j = 0; j < A[i]; j++) {
                dp[i][A[i]] += dp[i - 1][j];
            }
            dp[i][A[i]]++;
        }
        int total = 0;
        for (int i = 0; i < len; i++) {
            for (int j = L; j <= R; j++) {
                total += dp[i][j];
            }
        }
        return total;
    }

    public int numSubarrayBoundedMax2(int[] A, int L, int R) {
        /*
         * 思路：1、最大元素大于等于L，小于等于R = 最大元素小于等于R - 最大元素小于等于L-1
         * 
         */
        return find(A, R) - find(A, L - 1);
    }

    int find(int[] nums, int max) {
        int len = nums.length;
        int cont = 0;
        int total = 0;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            if (num <= max) {
                cont++;
                total += cont;
            } else {
                cont = 0;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[] a = { 3, 2, 1, 2, 3 };
        int L = 2;
        int R = 3;
        区间子数组个数 run = new 区间子数组个数();
        System.out.println(run.numSubarrayBoundedMax2(a, L, R));
    }
}
